package com.huawei.M01.iterator;

import java.util.Arrays;

/**
 * @author 111
 */
public class ThreeSumClosest {
    public int threeSumClosest(int[] nums, int target) {
        int result = Integer.MAX_VALUE;
        // 先排序
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {
            // 小优化，避免重复枚举
            if (i > 0 && nums[i] == nums[i + 1]) {
                continue;
            }
            int j = i + 1;
            int k = nums.length - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                // 如果sum正好等于target，则直接返回
                if (sum == target) {
                    return sum;
                }
                if (Math.abs(sum - target) < Math.abs(result - target)) {
                    result = sum;
                }
                // 确定左右端点
                if (sum > target) {
                    int k0 = k - 1;
                    while (k0 - 1 > j && nums[k0] == nums[k]) {
                        --k0;
                    }
                    k = k0;
                }else {
                    int j0 = j + 1;
                    while (j0 + 1 < k && nums[j0] == nums[j0 + 1]) {
                        j0++;
                    }
                    j = j0;
                }
            }
        }
        return result;
    }
}
